package algorithm;

import java.util.Arrays;

//最大子序列的和
public class LeetCode53 {
    public static void main(String[] args) {
        int[] arr = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int max = getNax(arr);
        System.out.println(max);
    }

    public static int getNax(int[] arr) {
        int[] dp = new int[arr.length];
        int max = arr[0];
        Arrays.fill(dp, 0);
        dp[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }
}
